扔鸡蛋问题的dp解法

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
在最坏的情况下，你确定 F 的值的最小移动次数是多少？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop

题目比较难理解的点在于“最坏情况”是什么意思

dp方法1

设dp[ i,j]表示在：目前试过的最高层为i，剩余鸡蛋数量为j的情况下，确定F的最小移动次数。

想要计算出dp[i,j]，那就得在第i层扔鸡蛋了（1次移动），根据鸡蛋的情况分为两种：

鸡蛋在第i层碎了，那么说明F<=i，i以上的层数不用考虑了，剩下j-1个鸡蛋。因此剩余需要考虑的最小移动次数=dp[i-1,j-1]
鸡蛋在第i层没有碎，说明F>=i，i以下的层数不用考虑了，剩下还是j个鸡蛋，网上的楼层有n-i层，把当前的第i层看作平地，那么上面的n-i层所需要的最小移动次数=dp[n-i, j]

这两种情况在扔鸡蛋的行为发生之后，只会出现一种，到底出现哪一种？由于题目说在“最坏情况”，所以我们选择的是移动次数更多的一种情况。

这个“选择”其实还是有点难理解的，因为在客观事实上，鸡蛋到底在哪一层刚刚好会碎掉，这明明是在我们进行实验之前就已经确定好的，不会因为我们的扔鸡蛋行为而改变才对。但题目的意思是，如果鸡蛋在第i层碎了，我们后续确定F的代价次数更多，那这个鸡蛋在第i层就是碎的；反之，如果它不碎给我们留下的待确定次数更多，那它就不碎。有一点“薛定谔的鸡蛋”的感觉，这个鸡蛋既可以碎，也可以不碎，它虽然原本和我们的扔鸡蛋行为是无关的，但在题目要求下，“是否碎”是由哪种情况会更麻烦来决定的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int k,n;
    cin>>k>>n;
    int dp[n+1][k+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j]=i;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=k;j++){
            for(int x=1;x<=i-1;x++){
                dp[i][j]=min(dp[i][j],1+max(dp[x-1][j-1],dp[i-x][j]));
            }
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}

dp方法2

设dp[k,m]表示k个鸡蛋，移动m次最多可以确定多少层楼。

例如dp[a,b]=c表示的意思是：有a个鸡蛋，最多可以移动b次，这个状态下，最坏情况下最多能确切测试一栋 c 层的楼。

因为我们的目的是确定n层楼，所以最终要计算的框架就是：

int superEggDrop(int K, int N) {
    int m = 0;
    while (dp[K][m] < N) {
        m++;
        // 状态转移...
    }
    return m;
}

那么当我们在k个鸡蛋，允许最多扔m次的状态下，选择在第X层扔鸡蛋的时候，就有两种情况：

鸡蛋碎了，我们少了一颗鸡蛋，用掉了一步，通过“鸡蛋碎了”这一结果我们可以确定它上面的N-X层肯定也会碎掉，F<=X，下面这部分的层数是dp[k-1,m-1]
鸡蛋没碎，鸡蛋的数量没有变，用掉了一步，通过“鸡蛋没碎”这一结果我们可以确定它下面的X-1层也不会碎掉，X<F，上面这部分的层数是dp[k,m-1]

但不论我们在哪一层楼扔鸡蛋，不论我们现在是否扔鸡蛋了，在k个鸡蛋，最多m次的这个状态下，能测算的楼层数已经确定了，就是“上面那部分”+“下面那部分”+1（扔鸡蛋的那层）
也就是：

dp[k,m]=1+dp[k-1,m-1]+dp[k,m-1]

并且由于m是一直在增加的，所以其实不需要二维数组来存储，一维就够了：

dp[k]=1+dp[k-1]+dp[k]

class Solution {
public:
    int superEggDrop(int K, int N) {
        int dp[K+1];
        for(int i=0;i<=K;i++){
            dp[i]=0;
        }
        int m=0;
        while(dp[K]<N){
            m++;
            for(int j=K;j>0;j--){
                dp[j]=dp[j-1]+dp[j]+1;
            }
        }
        return m;
    }
};